布隆过滤器（Bloom Filter）结构

核心特性

空间高效的概率型数据结构，用于判断 “元素是否存在”

特点：有假阳性（可能误判不存在的元素为存在），无假阴性（存在的元素一定能判断存在）

核心概念：位数组（存储二进制位）、多个哈希函数（将元素映射到位数组的多个索引）

代码实现（小顶堆）

class BloomFilter {
  constructor(size = 1024, hashCount = 3) {
    this.size = size; // 位数组大小（越大，假阳性率越低）
    this.hashCount = hashCount; // 哈希函数数量（越多，假阳性率越低，但插入/查询开销越大）
    this.bitArray = new Uint8Array(size).fill(0); // 位数组（用Uint8Array节省空间，每个元素存储8个二进制位）
  }

  // 哈希函数（简单版：基于不同种子计算哈希值）
  _hash(value, seed) {
    const strValue = String(value);
    let hash = 0;
    for (let i = 0; i < strValue.length; i++) {
      hash = (hash * seed + strValue.charCodeAt(i)) % this.size;
    }
    return hash;
  }

  // 添加元素
  add(value) {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this._hash(value, i + 1); // 不同种子生成不同哈希值
      const byteIndex = Math.floor(index / 8); // 计算所在字节的索引
      const bitIndex = index % 8; // 计算字节内的位索引
      this.bitArray[byteIndex] |= 1 << bitIndex; // 将对应位设为1
    }
  }

  // 判断元素是否存在（可能有假阳性）
  has(value) {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this._hash(value, i + 1);
      const byteIndex = Math.floor(index / 8);
      const bitIndex = index % 8;
      // 检查对应位是否为1，若有一个为0，则元素一定不存在
      if ((this.bitArray[byteIndex] & (1 << bitIndex)) === 0) {
        return false;
      }
    }
    return true; // 所有位都为1，元素可能存在（假阳性）
  }
}

适用场景

缓存穿透防护：如 Redis 缓存中，用布隆过滤器存储已存在的 key，查询时先通过布隆过滤器判断，不存在则直接返回，避免穿透到数据库

重复请求拦截：如用户频繁点击按钮发送请求，用布隆过滤器存储已发送的请求 ID，避免重复发送

大规模数据去重：如处理亿级用户 ID，用布隆过滤器快速判断 ID 是否已存在（无需存储完整 ID，节省空间）

注意

位数组大小和哈希函数数量需根据数据量调整（可通过公式计算最优值）

不适合需要 “精确判断存在” 的场景（如用户登录验证），适合 “允许少量误判” 的场景